import functools


class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        """
        :type maxChoosableInteger: int
        :type desiredTotal: int
        :rtype: bool
        """
        if maxChoosableInteger * (maxChoosableInteger - 1) // 2 < desiredTotal:
            return False
        @functools.cache
        def search(c, already):
            for i in range(maxChoosableInteger):
                if not (c >> i) & 1:
                    if already + i + 1 >= desiredTotal:
                        return True
                    else:
                        result = search(c ^ (1 << i), already + i + 1)
                        if not result:
                            return True
            return False

        return search(0, 0)


data = Solution()
maxChoosableInteger = 6
desiredTotal = 16
print(data.canIWin(maxChoosableInteger, desiredTotal))
